import java.util.Arrays;

/**
 * Created by L.jp
 * Description:你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，
 * 为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，
 * 那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
 * 给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，
 * 请你计算在不被发现的前提下最多的偷窃金额。
 * User: 86189
 * Date: 2022-09-05
 * Time: 10:30
 */
public class Solution {
    public int rob (int[] nums) {
        //方法其实和打家劫舍(一)的方法差不多，特别的地方就是第一家和最后一家是连着的，如果偷了最后一家就不能偷第一家，反过来也一样
        //中间的都是一样的偷法，所以就有两种值，一个是偷了第一家的，一个是没偷第一家的，两者取最大值即可
        if(nums.length==1){
            return nums[0];
        }
        //状态定义不变，dp[i]表示数组长度为i时的最多金额
        int[] dp=new int[nums.length+1];
        //偷第一家的初始化
        dp[1]=nums[0];
        int result1=0;
        //那么就不偷到最后一家
        for(int i=2;i< nums.length;i++){
            //中间的每一家都可以选择偷或者不偷，两者取最大值
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        result1=dp[nums.length-1];
        //第二次循环数组，选择不偷第一家，所以最后一家会被偷
        Arrays.fill(dp,0);
        dp[0]=0;
        for(int i=2;i<= nums.length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }
        return Math.max(result1,dp[nums.length]);
    }
}
